package _3sort.src;
/**
 * @className: _5
 * @description:
 * @author: myself
 * @date: 2025/7/16 21:07
 * @version: 0.1
 * @since: JDK17
 */
//快速排序：最坏O(n2)
    //随机展示，此时快速排序的时间复杂度变为O(nlogn)，对应的空间复杂度是logn
public class _5quickSort {
    public static void main(String[] args) {
        int[] s = {5,5, 4, 8, 3, 47, 56, 2, 4};
        System.out.print("原数组为：");
        for (int i = 0; i < s.length; i++) {
            System.out.print(s[i]+" ");
        }
        System.out.println();
        quickSort(s, 0, s.length - 1);
        System.out.print("将原数组从小到大排序为：");
        for (int i = 0; i < s.length; i++) {
            System.out.print(s[i]+" ");
        }
    }
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    private static void quickSort(int[] s, int n, int m) {
        if (n < m) {
            swap(s, n + (int) (Math.random() * (m - n + 1)), m);//随机获取数组中的一个数和最后一个值就行交换
            int[] p = partation(s, n, m);//返回的数组只有两个元素
            quickSort(s, n, p[0] - 1);//左侧排序
            quickSort(s, p[1] + 1,m);//右侧排序
        }
    }

    private static int[] partation(int[] s, int n, int m) {
        int left=n;//左分支
        int right = m;//右分支（不太算）
        int i=n;
        while (i < right) {//由于是要未排序的左右两侧的索引，因此在这里是小于，不是荷兰国旗的那种情况
            if (s[i] == s[m]) {
                i++;
            } else if (s[i] < s[m]) {
                swap(s, left++, i++);
            }else {
                swap(s, --right, i);//根据实际判断相关的索引，此时保留最后一个要判断的值（不做相关的交换），先对其他的进行交换，然后在最后进行交换
            }
        }
        swap(s, right, m);
        return new int[]{left, right};//返回的是所求数组相关的索引
    }
}